package com.atguigui.leetcode;

/**
 * 779.第K个语法符号
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/10/20 10:57
 */
public class P779KThSymbolInGrammar {

    public static void main(String[] args) {
        Solution solution = new P779KThSymbolInGrammar().new Solution();
        // TO TEST
    }

    class Solution {
        public int kthGrammar(int n, int k) {
            StringBuilder sb = new StringBuilder();
            sb.append(0);
            for (int i = 0; i < n; i++) {
                String str = sb.toString();
                sb.setLength(0);
                for (int j = 0; j < str.length(); j++) {
                    Integer num = Integer.valueOf(String.valueOf(str.charAt(j)));
                    if (num == 0) {
                        sb.append("01");
                    } else if (num == 1) {
                        sb.append("10");
                    }
                }
            }

            return Integer.valueOf(String.valueOf(sb.charAt(k - 1)));
        }


        public int kthGrammar2(int n, int k) {
            if (k == 1) {
                return 0; // 向上遍历到了第1行，则返回结果
            }
            if (k > (1 << n - 2)) {
                // 如果在“蓝色区间”，则与上一行值相反
                return 1 ^ kthGrammar(n - 1, k - (1 << n - 2));
            } else {
                // 如果在“黄色区间”，则与上一行值相同
                return kthGrammar(n - 1, k);
            }
        }

    }
}
